# -*- coding: utf-8 -*-
import numpy as np

class Node():
    def __init__(self, data=''):
        self.data = data
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.data)

class BuildTree():
    def __init__(self, firstData):
        self.rootNode = Node(firstData)
    def addNodes(self, NewDatas):
        Datalength = len(NewDatas)+1 # 1为根结点
        depth = np.floor(np.log2(Datalength)) + 1 # 树的深度
        i = 2
        stock = [self.rootNode] # 记录根节点的地址
        while i <= depth:
            currNN = 2**(i-1)
            j = 0
            while j < currNN:
                curr = stock[0]
                j += 1
                if NewDatas:
                    data = NewDatas.pop(0)
                else:
                    break;
                Node1 = Node(data)
                print('入节点数%d'%(data))
                if j % 2 == 0:
                    curr.right = Node1
                    stock.pop(0)
                    stock.append(Node1)
                else:
                    curr.left = Node1
                    stock.append(Node1)
            i += 1
        
line1 = [1,20,30,40,50,60,70,80]
B1 = BuildTree(line1[0])
B1.addNodes(line1[1:])

def preorder(root):
    p1 = []
    if root:
        p1.append(root.data)
        p1 += preorder(root.left)
        p1 += preorder(root.right)
    return p1

L1 = preorder(B1.rootNode)
print(L1)

def middle(root):
    p1 = []
    if root:
        p1 += middle(root.left)
        p1.append(root.data)
        p1 += middle(root.right)
    return p1

L1 = middle(B1.rootNode)
print(L1)

def post(root):
    p1 = []
    if root:
        p1 += post(root.left)
        p1 += post(root.right)
        p1.append(root.data)
    return p1

L1 = post(B1.rootNode)
print(L1)


        
